The present invention relates to a binary data compression and expansion processing apparatus which can compress and expand binary data at high speed and specifically perform parallel pipeline processing of binary data compressed by a Modified-Modified-Read (M.sup.2 R) method, thus improving capability of general purpose use, and which has associated circuits in one chip to allow low cost.
As a method for compressing and expanding binary data, coding methods, such as the MH method, the MR method, and the M.sup.2 R method, recommended by the CCITT, are internationally standardized, and are widely adopted. Among the three coding methods, i.e., the MH, MR, and M.sup.2 R methods, the M.sup.2 R method has the highest image compression efficiency.
The M.sup.2 R method is well known as a coding method for Group IV facsimile systems. In this method,
a. an End-Of-Line (EOL) code is omitted, PA1 b. a k parameter is set to be infinite, and PA1 c. all the bits of a reference line at the beginning of a page represent white pixels. PA1 a. decoding processing of code PA1 b. generation processing of image data for the decoded code
With these assumptions, a data compression ratio can be improved over that of the MR method. If a transmission error, if any, occurs, the error is sequentially transmitted to subsequent scanning lines as a principal problem. In order to prevent this, one-dimensional coding scanning lines are inserted in compression processing. The k parameter is the number of two-dimensional coding scanning lines between these one-dimensional coding scanning lines.
A conventional binary data compression and expansion processing apparatus has been realized in software, using a general-purpose microcomputer in order to perform expansion processing of encoded data according to these methods. In this processing, there is no problem when such an apparatus is applied to a facsimile system whose data transmission rate is limited to 9600 bps. However, when the conventional apparatus is used to display image data on work stations of a computer system, a good man-machine interface, for example, a page response time of 1/2 sec or less, cannot be achieved. Therefore, when the sequential expansion processing is executed in accordance with the M.sup.2 R method, the operating speed is considerably reduced, when compared with the MH method.
One cause of the above problem lies in the processing method of the entire system. More specifically, in a conventional system, decoding is performed in a bit serial manner. In order to solve the problem, parallel processing, advanced processing, and pipeline processing are widely utilized. The binary image data expansion processing can be apparently divided into:
Therefore, decoding and generation processing can be parallel-performed by separate hardware arrangements. In such arrangements, while a code is expanded, the next code is decoded, and the entire processing can be then pipelined. When binary data encoded by MH and MR methods is expanded, there is no problem in the advanced processing. However, the M.sup.2 R method has the following problems.
In all the MH, MR, and M.sup.2 R methods, the starting run of each line is always a white run and must be decoded to be white pixels. In the case of the MH and MR methods, an EOL code is used. Therefore, a decoding processing section which performs the advanced processing can detect the beginning of the next line due to the presence of an EOL code regardless of the progress of generation processing by a generation processing section.
However, since there is no EOL code in the M.sup.2 R method, the beginning of the next line can only be detected when the generation processing section develops each code and reaches an end of line. Therefore, if the beginning of the next line is indeterminate, it cannot be determined if the color of this portion is forcibly determined as white.
As a result, a decoding operation of a horizontal mode using separate code tables for a white run and a black run cannot be started in an advanced manner. More specifically, in the expansion processing of the M.sup.2 R method of a conventional apparatus, the advanced processing cannot be effectively performed.
Another cause of the problem of the operating speed is a problem of system configuration.
When the apparatus is operated in accordance with the MH coding method, image data on an immediately preceding line need not be input. However, in the MR and M.sup.2 R methods, image pattern data on a line or a reference line immediately preceding a corresponding processing line is referred to during compression and expansion processing.
This will be described with reference to expansion processing in a conventional compression and expansion processing apparatus. The compression and expansion processing apparatus exchanges image data with an external image memory through an image data bus, and designates an address of the external image memory through an image data address bus. The apparatus exchanges compressed encoded data through a code data bus. The apparatus is connected to a system bus of a microcomputer for controlling this apparatus to receive instructions and (at least a portion of) an address on the system bus. Image data obtained by expanding a code supplied through the code data bus is output onto the image data bus, and image pattern data on the reference line necessary for expansion processing of the current processing line is also read from the external image memory through the image data bus.
For this reason, in the MR and M.sup.2 R methods, a data transfer rate along the image data bus, which normally has to handle a large amount of data, often becomes a bottleneck of the total performance. Therefore, in the MR and M.sup.2 R methods, an expansion rate is considerably reduced, compared with the MH method.
Since the image memory logically has two-dimensional addresses, a complex circuit is required to convert them into one-dimensional physical addresses. In the apparatus, an image data address generator is normally important. However, even if the address generator is made of expensive high-quality components, this address generator cannot usually be utilized effectively in the system using this conventional compression and expansion processing apparatus.
In order to realize high-speed processing for other image processing functions, e.g., area extraction, enlargement, reduction, rotation, and the like, a similar address generator to that in the compression and expansion processing apparatus must often be provided to an external circuit.
In order to realize a compact, lightweight, low-cost system, an apparatus in which the aforementioned binary data compression and expansion processing apparatus is mounted on a semiconductor chip is commercially available. However, in the aforementioned apparatus, the image data bus must perform an output operation at the time of expansion and perform an input operation at the time of compression.
Therefore, driver and receiver I/O pins must be assigned to the respective pins of the image data bus. Also, since the code data bus must perform an input operation at the time of expansion and an output operation at the time of compression, it also requires both the driver and receiver I/O pins.
In addition, when the system utilizing this apparatus performs pipeline processing, a data flow direction is to be determined. For this purpose, the image data bus and the code data bus must be switched using a selector circuit, and double bus switching operations are required inside and outside of the apparatus.
Therefore, when the binary data compression and expansion processing apparatus is prepared as a semiconductor chip, it requires a large chip area. Since various system applications must be considered, the address generator incorporated in the apparatus cannot often cope with application requirements.
As described above, the conventional apparatus has problems in a processing rate, a capability of general purpose use.